package algorthm.systemTraning.binaryTree;
import java.io.IOException;
import java.util.*;
public class MaxSubBST{
       /*
		 分两种情况：
		 1. 以 head 为头的子树是 BST，则最大的节点数据是 1 + head.left数量 + head.right数据
		   1) 包括 head 整个数据是 BST 
		 2. 以 head 为头的子树不是 BST，则最大的节点数量是 max(head.left数量 , head.right数据)

       */
   public static class Info{
     public boolean isBST ;
     public int nodeCnt ;
     public int max ;
     public int min ;
     public Info(boolean isBST , int nodeCnt , int max , int min){
     	this.isBST = isBST ;
     	this.nodeCnt = nodeCnt ;
     	this.max = max ;
     	this.min = min ;
     }
   }
   public static int maxNodeSubBST(Node head){
   	   if(null == head) return 0;
   	   Info info = process(head);
   	   return info.nodeCnt ;
   }

   public static Info process(Node head){
	   if(null == head){
		   return new Info(true , 0 , Integer.MIN_VALUE , Integer.MAX_VALUE);
	   }
	   Info L = process(head.left);
	   Info R = process(head.right);
       
       int max = head.value;
       int min = head.value;
       int nodeCnt  = 0 ;
       if(null != L){
       	 max = Math.max(max , L.max);
       }
       if(null != R){
       	 max = Math.max(max , R.max);
       }
       if(null != L){
       	 min = Math.min(min , L.min);
       }
       if(null != R){
       	 min = Math.min(min , R.min);
       }
       boolean isBST = true;
       if(null != L && L.max >= head.value){
       	 isBST = false ;
       }
       if(null != R && R.min <= head.value){
       	 isBST = false ;
       }
       if(null != L && !L.isBST){
       	 isBST = false ;
       }
       if(null != R && !R.isBST){
       	 isBST = false ;
       }


       if(isBST){
       	  nodeCnt = L.nodeCnt + R.nodeCnt + 1;
       }else{
       	/* 如果 head 为头的树不是 BST ，则可以分成四种情况。
       	   1. 左右都不是 BST
       	   2. 左右都是 BST
       	   3. 左是 BST , 右不是
       	   4. 左不是 BST , 右是
       	*/
//       	  if(L.isBST && R.isBST){
//	          nodeCnt = Math.max(L.nodeCnt , R.nodeCnt) ;
//       	  }
//       	  if(!L.isBST && !R.isBST){
//			  nodeCnt = Math.max(L.nodeCnt , R.nodeCnt);
//		  }
//       	  if(L.isBST && !R.isBST){
//       	  	nodeCnt = Math.max(L.nodeCnt , R.nodeCnt);
//       	  }
//       	  if(!L.isBST && R.isBST){
//       	  	nodeCnt = Math.max(L.nodeCnt , R.nodeCnt) ;
//       	  }
       	  	nodeCnt = Math.max(L.nodeCnt , R.nodeCnt) ;
       }
       return new Info(isBST , nodeCnt , max , min);
   }

	// 为了验证
	// 对数器方法
	public static int right(Node head) {
		if (head == null) {
			return 0;
		}
		int h = getBSTSize(head);
		if (h != 0) {
			return h;
		}
		return Math.max(right(head.left), right(head.right));
	}

	// 为了验证
	// 对数器方法
	public static int getBSTSize(Node head) {
		if (head == null) {
			return 0;
		}
		ArrayList<Node> arr = new ArrayList<>();
		in(head, arr);
		for (int i = 1; i < arr.size(); i++) {
			if (arr.get(i).value <= arr.get(i - 1).value) {
				return 0;
			}
		}
		return arr.size();
	}

	// 为了验证
	// 对数器方法
	public static void in(Node head, ArrayList<Node> arr) {
		if (head == null) {
			return;
		}
		in(head.left, arr);
		arr.add(head);
		in(head.right, arr);
	}

	// 为了验证
	// 对数器方法
	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// 为了验证
	// 对数器方法
	public static Node generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	// 为了验证
	// 对数器方法
	public static void main(String[] args) throws IOException {
		int maxLevel = 4;
		int maxValue = 100;
		int testTimes = 1000000;
		System.out.println("测试开始");
		Drawing d = new Drawing();
		for (int i = 0; i < testTimes; i++) {
			Node head = generateRandomBST(maxLevel, maxValue);
			int i1 = maxNodeSubBST(head);
			int right = right(head);
			if (i1 != right) {
				System.out.println("出错了！i1:" + i1 + " , right:" + right);
				d.drawEntrance(head);
				System.out.println(printFromTopToBottom(head));

				break ;
			}
		}
		System.out.println("测试结束");
	}

    public static ArrayList<Integer> printFromTopToBottom(Node root) {
        ArrayList<Integer> res = new ArrayList<>();

        if (root == null)
            return res;

        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()){
            Node cur = q.poll();
            res.add(cur.value);
            if (cur.left!=null){
                q.add(cur.left);
            }
            if (cur.right != null)
                q.add(cur.right);
        }
        return res;
    }
}
